home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / voronoi_seg.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  4KB  |  226 lines
  1. #include <LEDA/voronoi.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/d_array.h>
  4. #include <LEDA/window.h>
  5.  
  6.  
  7.  
  8.  
  9. static  int segments_to_points(list<segment>& in, 
  10.                                list<point>& out, 
  11.                                d_array<point,segment>& D, double dist)
  12. { 
  13.   int count = 0;
  14.   segment s;
  15.  
  16.   forall(s,in)
  17.   { int n = int(s.length()/dist);
  18.     count = count + n +1;
  19.     double dx = (s.xcoord2() - s.xcoord1())/n;
  20.     double dy = (s.ycoord2() - s.ycoord1())/n;
  21.     double x  = s.xcoord1();
  22.     double y  = s.ycoord1();
  23.  
  24.     out.append(s.start());
  25.     D[s.start()] = s;
  26.  
  27.     for(int i = 0; i<n; i++)
  28.     {  x += dx + 0.001 * rrandom();
  29.        y += dy + 0.001 * rrandom();
  30.        point p(x,y);
  31.        D[p] = s;
  32.        out.append(p);
  33.      }
  34.  
  35. /*
  36.     out.append(s.end());
  37.     count++;
  38. */
  39.  
  40.    }
  41.  
  42.   out.permute();
  43.  
  44.  return count;
  45.  
  46. }
  47.  
  48. static  int polygons_to_points(list<polygon>& in, 
  49.                               list<point>& out, 
  50.                               d_array<point,segment>& D, int pixdist)
  51.  
  52. { polygon p;
  53.   int count = 0;
  54.  
  55.   forall(p,in)
  56.   { list<segment> sl = p.segments();
  57.     count += segments_to_points(sl,out,D,pixdist);
  58.    }
  59.   return count;
  60.  
  61.  }
  62.  
  63. /*
  64.  
  65. static  int circles_to_points(list<circle>& in, 
  66.                               list<point>& out, 
  67.                               d_array<point,circle>& D, double dist)
  68. { 
  69.   int count = 0;
  70.   circle s;
  71.  
  72.   forall(s,in)
  73.   { point c = s.center();
  74.     double r = s.radius();
  75.     int n = int(6.283 * r/dist);
  76.     count = count + n +1;
  77.     double alpha = 0;
  78.     double d = 6.283/n;
  79.  
  80.     for(int i = 0; i<n; i++)
  81.     {  point p = c.translate(alpha,r + 0.0001 * rrandom());
  82.        alpha += d;
  83.        D[p] = s;
  84.        out.append(p);
  85.      }
  86.    }
  87.  
  88.   out.permute();
  89.  
  90.  return count;
  91.  
  92. }
  93.  
  94. */
  95.  
  96.  
  97.  
  98. void VORONOI_SEG(list<segment>& sites, double R,GRAPH<point,point>& G, 
  99.                                                              int pixdist = 10)
  100. { 
  101.   list<point> pl;
  102.   d_array<point,segment> D;
  103.  
  104.   segments_to_points(sites,pl,D,pixdist);
  105.  
  106.   VORONOI(pl,R,G);
  107.  
  108.  
  109.   // eliminate edges intersecting segments
  110.  
  111.   list<edge> el;
  112.   edge e;
  113.   point p;
  114.  
  115.   forall_edges(e,G)  
  116.   { segment s = D[G[e]];
  117.     if (s.intersection(segment(G[source(e)],G[target(e)]),p)) el.append(e);
  118.    }
  119.  
  120.   forall(e,el) G.del_edge(e);
  121.  
  122.  
  123.  }
  124.  
  125.  
  126.  
  127. main()
  128. {
  129.  
  130.  window W;
  131.  
  132.  W.init(0,1000,0);
  133.  
  134.   segment s;
  135.   circle  c;
  136.   polygon p;
  137.  
  138.   double R = 1000;
  139.  
  140.   list<point>   pl;
  141.   list<segment> sl;
  142.   list<circle>  cl;
  143.   list<polygon> Pl;
  144.  
  145.   while ( W >> s ) 
  146.   { W << s;
  147.     sl.append(s);
  148.    }
  149.  
  150. /*
  151.   while ( W >> c ) 
  152.   { W << c;
  153.     cl.append(c);
  154.    }
  155.  
  156.   while ( W >> p ) 
  157.   { W << p;
  158.     Pl.append(p);
  159.    }
  160.  
  161. */
  162.  
  163.   int n = 10;
  164.  
  165.   cout << "Computing Voronoi diagram\n";
  166.   newline;
  167.  
  168.  
  169.   GRAPH<point,point> G;
  170.  
  171.     d_array<point,segment> D;
  172.     d_array<point,circle> D2;
  173.   
  174.     int count = segments_to_points(sl,pl,D,n/W.scale());
  175.  
  176.             //+ circles_to_points(cl,pl,D2,n)
  177.             //+ polygons_to_points(Pl,pl,D,n);
  178.  
  179.     cout << count << " points generated.\n";
  180.     newline;
  181.  
  182.  
  183.     pl.append(point(-5000,-5000));
  184.     pl.append(point(-5000,5000));
  185.     pl.append(point(5000,5000));
  186.     pl.append(point(5000,-5000));
  187.  
  188.   
  189.     VORONOI(pl,R,G);
  190.  
  191.     edge e;
  192.  
  193.  
  194. /*
  195.     forall_edges(e,G) W.draw_segment(G[source(e)], G[target(e)]);
  196.     W.read_mouse();
  197. */
  198.  
  199.     // eliminate edges intersecting segments
  200.  
  201.     list<edge> el;
  202.  
  203.     edge_array<edge> rev(G);
  204.  
  205.     compute_correspondence(G,rev);
  206.  
  207.     edge_array<int> deleted(G,false);
  208.   
  209.     forall_edges(e,G)  
  210.      if (!deleted[e])
  211.      { segment s = D[G[e]];
  212.        segment t = segment(G[source(e)], G[target(e)]);
  213.        point p;
  214.        if (s.intersection(t,p)) deleted[e] = deleted[rev[e]] = true;
  215.       }
  216.  
  217.     W.set_line_width(2);
  218.  
  219.     forall_edges(e,G) 
  220.         if (!deleted[e]) W.draw_segment(G[source(e)], G[target(e)],blue);
  221.  
  222.     W.read_mouse();
  223.  
  224.     return 0;
  225. }
  226.